Trong cuộc chiến với Taliban ông được phong làm tư lệnh quân đội của người Uzbek chống lại Taliban và cũng là đồng minh của Hoa Kỳ trong cuộc chiến này. Bên cạnh việc nhận được sự hỗ trợ to lớn của Hoa Kỳ trong cuộc chiến này nhưng không thể phủ nhận tài dùng binh của ông. Trong một cuộc tấn công, Dostum đã chỉ huy quân đội của mình thần tốc tiến vào thành phố Mazar-e-Sharif từ phía Nam và Đông Nam với sự giúp đỡ của 4.000 chiến binh Taliban đã đào ngũ và đã chiếm được thành phố cửa ngõ phía bắc của Afghanistan trước khi các lực lượng biệt kích của Mỹ định chiếm lấy nó. Đây được coi là một thắng lợi chiến lược của Liên minh phương Bắc, giúp họ nâng vị thế đàm phán của mình khi Mỹ dùng bộ binh đổ bộ vào chiếm cứ Afghanistan.[6]

Trong cuộc chiến này, ông tỏ ra sất mạnh mẽ khi kiên quyết tấn công lực lượng Taliban. Có tin cho rằng tướng Dostum đã giết đến 600 lính Taliban khi ông dẫn lực lượng của mình tiến vào Mazar-i-Sharif. Đó cũng là nguyên nhân cho cuộc nổi loạn đẫm máu do những tù binh Taliban người nước ngoài nổ ra tại một trại giam giữ lính Taliban gần Mazar-i-Sharif ngày 25 tháng 11 năm 2001.[7] Ông cũng là người chỉ huy quân Liên minh phương Bắc tấn công và chiếm được Kunduz sau hơn 12 ngày vây hãm và là người tiếp quản thành phố này.[8] Cuộc tấn công diễn ra ác liệt kéo dài đến sáu tiếng đồng hồ và cuối cùng quân Liên minh phương Bắc, dưới sự chỉ huy của tướng Dostum đã tràn vào chiếm được Kunduz.[9]

Xung quanh việc chiếm đóng này, có những cáo buộc về nhân quyền nhắm vào ông khi có khoảng 2.000 tay súng Taliban đầu hàng Dostum tại tỉnh Kunduz vào tháng 11 năm 2001 đã bị chết ngạt trong các xe chở hàng khi họ được đưa tới các trại giam. Theo họ thì ông đã ra lệnh nhồi nhét tù binh Taliban vào trong những thùng chở hàng (shipping containers) rồi để cho họ chết ngạt, báo giới gọi là vụ thảm sát khét tiếng Dasht-i-Laili. Đồng thời 300 tù binh Taliban khác do Dostum phối hợp cầm giữ trong một nhà tù chết sau đó trong một cuộc dấy loạn.[10] Trong cuộc chiến này cũng có những thông tin cho rằng ông đã trao cho Mỹ những tù binh bị tình nghị là thành viên Taliban và Al Qaeda để đổi lại những khoản tiền thưởng của CIA, mỗi tù binh giao nộp sẽ được chi từ 3.000 USD đến 25.000 USD[11]

Khi cuộc chiến đến hồi kết. Dostum đã tranh thủ phát triển lực lượng riêng cho mình bằng cách chiếm đoạn các vũ khí và khí tài chiến tranh cũng như chiêu hàng các chiến binh Taliban về đầu quân cho ông khi lực lượng của ông chiếm đóng các lãnh thổ thuộc quyền kiểm soát của Taliban. Điển hình là trong cuộc chiếm đóng thành phố Kunduz, có thông tin cho rằng ông đã để cho khoảng 2.000 người Uzbekistan đầu quân cho Taliban, dưới sự chỉ huy của một người tên là Juma Namangani (từng là lính dù trong Hồng quân Liên Xô) chạy về phương bắc vốn là lãnh địa của ông.[12] Những hành động như vậy hoàn toàn không làm hài lòng các sứ quân khác, và kết quả là xuất hiện những mâu thuẫn trầm trọng giữa các sứ quân trong liên minh phương Bắc.